package sliding_window

/*
1248.给你一个整数数组nums 和一个整数 k。如果某个连续子数组中【恰好】有 k 个奇数数字，我们就认为这个子数组是「优美子数组」。
请返回这个数组中 「优美子数组」 的数目。

示例 1：
输入：nums = [1,1,2,1,1], k = 3
输出：2
解释：包含 3 个奇数的子数组是 [1,1,2,1] 和 [1,2,1,1] 。

示例 2：
输入：nums = [2,4,6], k = 1
输出：0
解释：数列中不包含任何奇数，所以不存在优美子数组。

示例 3：
输入：nums = [2,2,2,1,2,2,1,2,2,2], k = 2
输出：16
*/

/*
Time O(N) for one pass
Space O(1)
*/
func numberOfSubArrays(nums []int, k int) int {
	return atMostNumberOfSubArrays(nums, k) - atMostNumberOfSubArrays(nums, k-1)
}

//最多有k个奇数数字
func atMostNumberOfSubArrays(nums []int, k int) int {
	res, left, right := 0, 0, 0
	//expand windows
	for right < len(nums) {
		k -= nums[right] % 2
		//shrink windows
		for k < 0 {
			k += nums[left] % 2
			left++
		}
		res += right - left + 1
		right++
	}
	return res
}

//Actually it's same as three pointers.
//Though we use count to count the number of even numbers.
func numberOfSubArrays3Pointer(nums []int, k int) int {
	res, left, right, count := 0, 0, 0, 0
	for right < len(nums) {
		if nums[right]%2 == 1 {
			k--
			count = 0
		}

		for k == 0 {
			k += nums[left] & 1
			left++
			count++
		}
		right++
		res += count
	}
	return res
}

//数学方法：满足 l∈(odd[i−1],odd[i]] 且 r∈[odd[i+k−1],odd[i+k]) 条件的子数组 [l,r] 包含 [odd[i],odd[i+k−1]] 且 [l,r] 里的奇数个数为 k 个
//因此对于第 i个奇数，它对答案的贡献为符合条件的 [l,r] 的个数:
//(odd[i]−odd[i−1])×(odd[i+k]−odd[i+k−1])
func numberOfSubArraysMath(nums []int, k int) int {
	ans, cnt, n := 0, 0, len(nums)
	odd := make([]int, n+2)
	for i := 0; i < n; i++ {
		if (nums[i] & 1) != 0 {
			cnt++
			odd[cnt] = i //odd[奇数个数]=奇数下标值

		}
	}

	odd[0] = -1
	cnt++
	odd[cnt] = n
	for i := 1; i+k <= cnt; i++ {
		ans += (odd[i] - odd[i-1]) * (odd[i+k] - odd[i+k-1])
	}
	return ans
}

//前缀和
func numberOfSubArraysPreSum(nums []int, k int) int {
	res, sum := 0, 0
	prefixCnt := make([]int, len(nums)+1) //下标为前缀和，值为前缀和的个数
	prefixCnt[0] = 1
	//遍历原数组，计算当前前缀和，并统计到prefixCnt中
	//并累加与当前前缀和差值为k的前缀和的个数
	for _, v := range nums {
		sum += v & 1
		prefixCnt[sum]++

		if sum >= k {
			res += prefixCnt[sum-k]
		}
	}
	return res
}
